package com.zhugang.week13.linkedlist;

/**
 * @program algorithms
 * @description: hasCycel2
 * @author: chanzhugang
 * @create: 2022/09/09 17:41
 */
public class HasCycle2 {

    /**
     * 141 环形链表
     * https://leetcode.cn/problems/linked-list-cycle/
     * 时间复杂度：O(n)
     * 空间复杂度 : O(1)
     *
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        // 快慢指针法
        if (head == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null && fast != slow) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast == slow) {
            return true;
        }
        return false;
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}